package com.mlh.binarytree.search;

import com.mlh.binarytree.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * @author 缪林辉
 * @date 2024/3/25 14:19
 * @DESCRIPTION
 */
public class InorderTraversal {
    //方法一：递归
    public List<Integer> method1(TreeNode root) {
        List<Integer> res=new ArrayList<>();
        recursion(root,res);
        return res;
    }

    public void recursion(TreeNode node,List<Integer>list){
        if(node==null){
            return;
        }
        recursion(node.left,list);
        list.add(node.val);
        recursion(node.right,list);
    }

    //方法二：栈
    //将左子树的左边界全部入栈
    //出栈，打印
    //对其右子树进行相同的操作
    public List<Integer> method2(TreeNode root) {
        if(root==null){
            return new ArrayList<>();
        }
        ArrayList<Integer> res = new ArrayList<>();
        Stack<TreeNode>stack=new Stack<>();
        TreeNode node=root;
        stack.push(root);
        while (node.left!=null){
            node=node.left;
            stack.push(node);
        }
        while (!stack.isEmpty()){
            node=stack.pop();
            res.add(node.val);
            node=node.right;
            while (node!=null){
                stack.push(node);
                node=node.left;
            }
        }
        return res;
    }

    public List<Integer> practice(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        recursionPractice(root,list);
        return list;
    }

    private void recursionPractice(TreeNode root, ArrayList<Integer> list) {
        if(root==null){
            return;
        }
        recursionPractice(root.left,list);
        list.add(root.val);
        recursionPractice(root.right,list);
    }

    public List<Integer> practice2(TreeNode root) {
      ArrayList<Integer>res=new ArrayList<>();
      recursionPractice2(root,res);
      return res;
    }

    private void recursionPractice2(TreeNode root, ArrayList<Integer> list) {
        if(root==null){
            return;
        }
        recursionPractice2(root.left,list);
        list.add(root.val);
        recursionPractice2(root.right,list);
    }

    public List<Integer> method2Practice(TreeNode root) {
        LinkedList<TreeNode>stack=new LinkedList<>();
        while(root!=null){
            stack.addLast(root);
            root=root.left;
        }
        ArrayList<Integer>res=new ArrayList<>();
        while(!stack.isEmpty()){
            TreeNode pop = stack.pollLast();
            res.add(pop.val);
            pop=pop.right;
            while(pop!=null){
                stack.add(pop);
                pop=pop.left;
            }
        }
        return res;
    }
}
